package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 222. 完全二叉树的节点个数
 * 二分查找 + 位运算
 * 因此对于最大层数为 hh 的完全二叉树，节点个数一定在 [2^h,2^{h+1}-1]的范围内，
 * 可以在该范围内通过二分查找的方式得到完全二叉树的节点个数
 *
 * @author fy
 * @date 2022/4/19 21:00
 */
public class Solution222_1 {

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        TreeNode node = root;
        while (node.left != null) {
            depth++;
            node = node.left;
        }
        // 2^h
        int low = 1 << depth;
        // 2^{h+1}-1
        int high = (1 << (depth + 1)) - 1;
        while (low < high) {
            int mid = low + ((high - low + 1) >> 1);
            // 如果存在, 则在更右边, 否则在更左边
            if (exists(root, depth, mid)) {
                low = mid;
            } else {
                high = mid -1;
            }
        }
        return low;
    }

    /**
     * 查找树中在level层是否存在第k个节点
     *
     * @param root
     * @param level
     * @param k
     * @return
     */
    private boolean exists(TreeNode root, int level, int k) {
        // 2^{h-1}
        int bits = 1 << (level - 1);
        /**
         *     1            h = 0
         *    / \
         *   2   3          h = 1
         *  / \  /
         * 4  5 6           h = 2
         *
         * 现在这个树中的值都是节点的编号，最底下的一层的编号是[2^h ，2^h - 1]，现在h = 2，也就是4, 5, 6, 7。
         * 4, 5, 6, 7对应二进制分别为 100 101 110 111 不看最左边的1，从第二位开始，0表示向左，1表示向右，正好可以表示这个节点相对于根节点的位置。
         * 比如4的 00 就表示从根节点 向左 再向左。6的 10 就表示从根节点 向右 再向左
         *
         * 那么想访问最后一层的节点就可以从节点的编号的二进制入手。从第二位开始的二进制位表示了最后一层的节点相对于根节点的位置。
         * 那么就需要一个bits = 2^(h - 1) 上面例子中的bits就是2，对应二进制为010。这样就可以从第二位开始判断。（树三层高，需要向左或向右走两次才能到叶子）
         * 比如看5这个节点存不存在，先通过位运算找到编号为5的节点相对于根节点的位置。010 & 101 发现第二位是0，说明从根节点开始，第一步向左走。
         * 之后将bit右移一位，变成001。001 & 101 发现第三位是1，那么第二步向右走。
         * 最后bit为0，说明已经找到编号为5的这个节点相对于根节点的位置，看这个节点是不是空，不是说明存在，exist返回真
         * 编号为5的节点存在，说明总节点数量一定大于等于5。所以二分那里low = mid
         *
         * 再比如看7存不存在，010 & 111 第二位为1，第一部从根节点向右；001 & 111 第三位也为1，第二步继续向右。
         * 然后判断当前节点是不是null，发现是null，exist返回假。
         * 编号为7的节点不存在，说明总节点数量一定小于7。所以high = mid - 1
         */
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }

}
